{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Number of Good Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfGoodSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #好子集的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;。如果&nbsp;<code>nums</code>&nbsp;的一个子集中，所有元素的乘积可以表示为一个或多个 <strong>互不相同的质数</strong> 的乘积，那么我们称它为&nbsp;<strong>好子集</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果&nbsp;<code>nums = [1, 2, 3, 4]</code>&nbsp;：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><code>[2, 3]</code>&nbsp;，<code>[1, 2, 3]</code>&nbsp;和&nbsp;<code>[1, 3]</code>&nbsp;是 <strong>好</strong>&nbsp;子集，乘积分别为&nbsp;<code>6 = 2*3</code>&nbsp;，<code>6 = 2*3</code>&nbsp;和&nbsp;<code>3 = 3</code>&nbsp;。</li>\n",
    "\t\t<li><code>[1, 4]</code> 和&nbsp;<code>[4]</code>&nbsp;不是 <strong>好</strong>&nbsp;子集，因为乘积分别为&nbsp;<code>4 = 2*2</code> 和&nbsp;<code>4 = 2*2</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>nums</code>&nbsp;中不同的&nbsp;<strong>好</strong>&nbsp;子集的数目对<em>&nbsp;</em><code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;的结果。</p>\n",
    "\n",
    "<p><code>nums</code>&nbsp;中的 <strong>子集</strong>&nbsp;是通过删除 <code>nums</code>&nbsp;中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>好子集为：\n",
    "- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。\n",
    "- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。\n",
    "- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。\n",
    "- [2]：乘积为 2 ，可以表示为质数 2 的乘积。\n",
    "- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。\n",
    "- [3]：乘积为 3 ，可以表示为质数 3 的乘积。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,2,3,15]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>好子集为：\n",
    "- [2]：乘积为 2 ，可以表示为质数 2 的乘积。\n",
    "- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。\n",
    "- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。\n",
    "- [3]：乘积为 3 ，可以表示为质数 3 的乘积。\n",
    "- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-number-of-good-subsets](https://leetcode.cn/problems/the-number-of-good-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-number-of-good-subsets](https://leetcode.cn/problems/the-number-of-good-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[4,2,3,15]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        lst=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(n):\n",
    "            state = 0\n",
    "            for i, x in enumerate(lst):\n",
    "                while n > 0 and n % x == 0:\n",
    "                    if (state >> i) & 1 == 1:\n",
    "                        return False,state\n",
    "                    state |= (1 << i)\n",
    "                    n //= x\n",
    "                    if n == 1:\n",
    "                        return True,state\n",
    "\n",
    "        cnt={}\n",
    "        mask=1<<10\n",
    "        f=[0]*mask\n",
    "        f[0]=1\n",
    "        mod=10**9+7\n",
    "\n",
    "        for x in nums:\n",
    "            times=cnt.get(x,0)+1\n",
    "            cnt[x]=times\n",
    "\n",
    "\n",
    "        for i in range(2,31):\n",
    "            if i not in cnt:\n",
    "                continue\n",
    "            (flag,cur)=check(i)\n",
    "            if flag==False:\n",
    "                continue\n",
    "            for pre in range(mask-1,-1,-1):\n",
    "                if (pre&cur) != 0:\n",
    "                    continue\n",
    "                s=pre|cur\n",
    "                f[s]+=f[pre]*cnt[i]%mod\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(1,mask):\n",
    "            ans=(ans+f[i])%mod\n",
    "        if 1 in cnt:\n",
    "            ans=(ans*2**cnt[1])%mod\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力枚举失败\n",
    "        # def f(n):\n",
    "        #     state=0\n",
    "        #     count=0\n",
    "        #     for i,x in enumerate(lst):\n",
    "        #         while n>0 and n%x==0:\n",
    "        #             if (state>>i)&1==1:\n",
    "        #                 return False\n",
    "        #             state|=(1<<i)\n",
    "        #             n//=x\n",
    "        #             if n==1:\n",
    "        #                 return True\n",
    "                \n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if f(res) else 0\n",
    "        #     a=dfs(i-1,res)\n",
    "        #     b=dfs(i-1,res*nums[i])\n",
    "        #     return a+b\n",
    "        # return dfs(n-1,1)\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        # 互不相同的质数;;质数分解之后不能有一样的\n",
    "        # 1 <= nums.length <= 10^5\n",
    "        # 1 <= nums[i] <= 30  ；； 显然这是一个关键的条件\n",
    "        # 不能够选的数 [4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28]\n",
    "        m = Counter(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums = [x for x in nums if x not in [1, 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28]]\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        # 强行暴力回溯就完事了\n",
    "        def f(i, t):\n",
    "            if i >= n:\n",
    "                if t:\n",
    "                    nonlocal ans\n",
    "                    s = 1\n",
    "                    for v in t:\n",
    "                        s *= m[v]\n",
    "                    ans += s\n",
    "                return\n",
    "            f(i + 1, t)\n",
    "            x = nums[i]\n",
    "            if all(gcd(x, y) == 1 for y in t):\n",
    "                t1 = list(t)\n",
    "                t1.append(x)\n",
    "                f(i + 1, tuple(t1))\n",
    "        \n",
    "        ans = 0\n",
    "        f(0, tuple())\n",
    "\n",
    "        return ((2**m[1]) * ans) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "N = 10\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "\n",
    "        counter = Counter(nums)\n",
    "\n",
    "        dp = [0] * (1 << N)\n",
    "        dp[0] = pow(2, counter[1], MOD)\n",
    "\n",
    "        for elem, cnt in counter.items():\n",
    "            if elem == 1:\n",
    "                continue\n",
    "\n",
    "            substate = 0\n",
    "            for i, prime in enumerate(primes):\n",
    "                if elem % (prime * prime) == 0:\n",
    "                    break\n",
    "\n",
    "                if elem % prime == 0:\n",
    "                    substate |= 1 << i\n",
    "            else:\n",
    "                for state in range((1 << N) - 1, 0, -1):\n",
    "                    if state & substate == substate:\n",
    "                        dp[state] = (dp[state] + dp[state ^ substate] * cnt) % MOD\n",
    "\n",
    "        return sum(dp[1: ]) % MOD        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    " \n",
    "        single = [2,3,5,7,11,13,17,19,23,29]\n",
    "        counter = Counter(nums)\n",
    "        MOD = 10**9+7 \n",
    "        def getMask(n):\n",
    "            ret = 0\n",
    "            for i in range(len(single)):\n",
    "                div = single[i]\n",
    "                if n<div:\n",
    "                    break \n",
    "                if n%div==0:\n",
    "                    if n%(div**2)==0:\n",
    "                        return 0 \n",
    "                    ret = ret|(1<<(i+1))\n",
    "            # print(n,ret)\n",
    "            return ret \n",
    "        keys = [k for k in counter.keys() if getMask(k)>0]\n",
    "        stack = []\n",
    "        ret = 0\n",
    "        dp = {}\n",
    "        def dfs(i,mask,ans):\n",
    "            if i==len(keys):\n",
    "                return 0 \n",
    "            k = keys[i]\n",
    "            nmask = getMask(k)\n",
    "            sret = 0\n",
    "            if mask&nmask==0:\n",
    "                curAns = ans*counter[k]%MOD\n",
    "                sret = (dfs(i+1,mask|nmask,curAns)+curAns)%MOD\n",
    "            sret = (dfs(i+1,mask,ans)+sret)%MOD\n",
    "            \n",
    "            return sret\n",
    "        ret = dfs(0,0,1)\n",
    "        # print(keys,counter,ret)\n",
    "        if 1 in counter:\n",
    "            # c33+c32+c31\n",
    "            ret = ret*(2**counter[1])%MOD \n",
    "        return ret \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def qpow(self, x, y):\n",
    "        res = 1\n",
    "        while y > 0:\n",
    "            if y % 2 == 1: res = (res * x) % M\n",
    "            x = (x * x) % M\n",
    "            y //= 2\n",
    "        return res\n",
    "\n",
    "    def dfs(self, d, kv, s, ans, i):\n",
    "        if i == len(kv): return ans\n",
    "        res = self.dfs(d, kv, s, ans, i + 1)\n",
    "        s_c = d[kv[i][0]]\n",
    "        if s.isdisjoint(s_c):\n",
    "            res += self.dfs(d, kv, s.union(s_c), ans * kv[i][1], i + 1)\n",
    "        return res % M\n",
    "\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        d = {1: set(), 2: {2}, 3: {3}, 5: {5}, 6: {2, 3}, 7: {7},\n",
    "             10: {2, 5}, 11: {11}, 13: {13}, 14: {2, 7}, 15: {3, 5},\n",
    "             17: {17}, 19: {19}, 21: {3, 7}, 22: {2, 11}, 23: {23},\n",
    "             26: {2, 13}, 29: {29}, 30: {2, 3, 5}}\n",
    "        d2 = {}\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d2[num] = d2.get(num, 0) + 1\n",
    "        x = d2.pop(1, 0)\n",
    "        y = self.qpow(2, x)\n",
    "        if not d2: return 0\n",
    "        kv = list(d2.items())\n",
    "        for i in range(len(kv)):\n",
    "            k, v = kv[i]\n",
    "            res = (res + self.dfs(d, kv, d[k], v, i + 1)) % M\n",
    "        return (res * y) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = pow(2, cnt[1], MOD)  # 用 1 组成空质数集合的方案数\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:  # x 是 SF\n",
    "                j = other = (M - 1) ^ mask  # mask 的补集\n",
    "                while True:  # 枚举 other 的子集 j\n",
    "                    f[j | mask] = (f[j | mask] + f[j] * c) % MOD  # 不选 mask + 选 mask\n",
    "                    j = (j - 1) & other\n",
    "                    if j == other: break\n",
    "        return (sum(f) - pow(2, cnt[1], MOD)) % MOD  # -1 表示去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    " \n",
    "        single = [2,3,5,7,11,13,17,19,23,29]\n",
    "        counter = Counter(nums)\n",
    "        MOD = 10**9+7 \n",
    "        def getMask(n):\n",
    "            ret = 0\n",
    "            for i in range(len(single)):\n",
    "                div = single[i]\n",
    "                if n<div:\n",
    "                    break \n",
    "                if n%div==0:\n",
    "                    if n%(div**2)==0:\n",
    "                        return 0 \n",
    "                    ret = ret|(1<<(i+1))\n",
    "            # print(n,ret)\n",
    "            return ret \n",
    "        keys = [k for k in counter.keys() if getMask(k)>0]\n",
    "        stack = []\n",
    "        ret = 0\n",
    "        def dfs(i,mask,ans):\n",
    "            if i==len(keys):\n",
    "                return 0 \n",
    "            k = keys[i]\n",
    "            nmask = getMask(k)\n",
    "            nonlocal ret \n",
    "            if mask&nmask==0:\n",
    "                curAns = ans*counter[k]%MOD\n",
    "                ret = (ret+curAns)%MOD\n",
    "                dfs(i+1,mask|nmask,curAns)\n",
    "            dfs(i+1,mask,ans)\n",
    "        dfs(0,0,1)\n",
    "        # print(keys,counter,ret)\n",
    "        if 1 in counter:\n",
    "            # c33+c32+c31\n",
    "            ret = ret*(2**counter[1])%MOD \n",
    "        return ret \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        counter = Counter(nums)\n",
    "        f = [0] * 1024\n",
    "        M = 10 ** 9 + 7\n",
    "        f[0] = 1\n",
    "        for k, v in counter.items():\n",
    "            if k == 1:\n",
    "                continue\n",
    "            state = 0\n",
    "            for i in range(10):\n",
    "                if k % primes[i] == 0:\n",
    "                    k //= primes[i]\n",
    "                    if k % primes[i] == 0:\n",
    "                        state = -1\n",
    "                        break\n",
    "                    state |= 1 << i\n",
    "            if state == -1:\n",
    "                continue\n",
    "            for i in range(1024):\n",
    "                if f[i] and (i & state == 0):\n",
    "                    f[i ^ state] = (f[i] * v + f[i ^ state]) % M\n",
    "        return  (sum(f[1:]) << counter[1]) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        ct, mod = Counter(nums), 10**9+7\n",
    "        d = defaultdict(int)\n",
    "        d[1] = (1 << ct[1]) % mod\n",
    "        for num in [2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30]:\n",
    "            for x in list(d):\n",
    "                if math.gcd(num, x) == 1:\n",
    "                    d[num*x] += ct[num]*d[x]\n",
    "                    d[num*x] %= mod\n",
    "        return (sum(d.values())-d[1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        lst=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(n):\n",
    "            state = 0\n",
    "            for i, x in enumerate(lst):\n",
    "                while n > 0 and n % x == 0:\n",
    "                    if (state >> i) & 1 == 1:\n",
    "                        return False,state\n",
    "                    state |= (1 << i)\n",
    "                    n //= x\n",
    "                    if n == 1:\n",
    "                        return True,state\n",
    "\n",
    "        cnt=Counter(nums)\n",
    "        mask=1<<10\n",
    "        f=[0]*mask\n",
    "        f[0]=1\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        for i in range(2,31):\n",
    "            if i not in cnt:\n",
    "                continue\n",
    "            (flag,cur)=check(i)\n",
    "            if flag==False:\n",
    "                continue\n",
    "            for pre in range(mask-1,-1,-1):\n",
    "                if (pre&cur) != 0:\n",
    "                    continue\n",
    "                s=pre|cur\n",
    "                f[s]+=f[pre]*cnt[i]%mod\n",
    "        \n",
    "        ans=0\n",
    "        ans=sum(f)-1\n",
    "        if 1 in cnt:\n",
    "            ans=(ans*2**cnt[1])%mod\n",
    "        return ans%mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力枚举失败\n",
    "        # def f(n):\n",
    "        #     state=0\n",
    "        #     count=0\n",
    "        #     for i,x in enumerate(lst):\n",
    "        #         while n>0 and n%x==0:\n",
    "        #             if (state>>i)&1==1:\n",
    "        #                 return False\n",
    "        #             state|=(1<<i)\n",
    "        #             n//=x\n",
    "        #             if n==1:\n",
    "        #                 return True\n",
    "                \n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if f(res) else 0\n",
    "        #     a=dfs(i-1,res)\n",
    "        #     b=dfs(i-1,res*nums[i])\n",
    "        #     return a+b\n",
    "        # return dfs(n-1,1)\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        lst=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(n):\n",
    "            state = 0\n",
    "            for i, x in enumerate(lst):\n",
    "                while n > 0 and n % x == 0:\n",
    "                    if (state >> i) & 1 == 1:\n",
    "                        return False,state\n",
    "                    state |= (1 << i)\n",
    "                    n //= x\n",
    "                    if n == 1:\n",
    "                        return True,state\n",
    "\n",
    "        cnt=Counter(nums)\n",
    "        mask=1<<10\n",
    "        f=[0]*mask\n",
    "        f[0]=1\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        for i in range(2,31):\n",
    "            if i not in cnt:\n",
    "                continue\n",
    "            (flag,cur)=check(i)\n",
    "            if flag==False:\n",
    "                continue\n",
    "            for pre in range(mask):\n",
    "                if (pre&cur) != 0:\n",
    "                    continue\n",
    "                s=pre|cur\n",
    "                f[s]+=f[pre]*cnt[i]%mod\n",
    "        \n",
    "        ans=0\n",
    "        ans=sum(f)-1\n",
    "        if 1 in cnt:\n",
    "            ans=(ans*2**cnt[1])%mod\n",
    "        return ans%mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力枚举失败\n",
    "        # def f(n):\n",
    "        #     state=0\n",
    "        #     count=0\n",
    "        #     for i,x in enumerate(lst):\n",
    "        #         while n>0 and n%x==0:\n",
    "        #             if (state>>i)&1==1:\n",
    "        #                 return False\n",
    "        #             state|=(1<<i)\n",
    "        #             n//=x\n",
    "        #             if n==1:\n",
    "        #                 return True\n",
    "                \n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if f(res) else 0\n",
    "        #     a=dfs(i-1,res)\n",
    "        #     b=dfs(i-1,res*nums[i])\n",
    "        #     return a+b\n",
    "        # return dfs(n-1,1)\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "target = [i for i in range(2, 31)]\n",
    "for i in (4,8,12,16,20,24,28,9,18,27,25):\n",
    "    target.remove(i)\n",
    "prime = {2,3,5,7,11,13,17,19,23,29}\n",
    "pn = len(prime)\n",
    "mask = [0] * 31\n",
    "for t in target:\n",
    "    for j, p in enumerate(prime):\n",
    "        if t % p == 0:\n",
    "            mask[t] |= (1 << j)\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        mod = int(10**9+7)\n",
    "        cnt = Counter(nums)\n",
    "        dp = [0] * (1 << pn)\n",
    "        dp[0] = 1\n",
    "        for t in target:\n",
    "            if cnt[t] != 0:\n",
    "                for j in range((1 << pn) - 1, mask[t] - 1, -1):\n",
    "                    if (mask[t] | j) == j:\n",
    "                        dp[j] += (dp[j ^ mask[t]] * cnt[t]) % mod\n",
    "        res = sum(dp) % mod\n",
    "        return ((res - 1)* pow(2, cnt[1], mod)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  #\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:\n",
    "                for j in range(M - 1, -1, -1):\n",
    "                    if mask & j == 0:\n",
    "                        f[mask | j] = (f[mask | j] + f[j] * c) % MOD\n",
    "        # print(f)\n",
    "        return (sum(f) * pow(2, cnt[1], MOD) - pow(2, cnt[1], MOD)) % MOD  # -1 表示去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, d, kv, s, ans, i):\n",
    "        if i == len(kv): return ans\n",
    "        res = self.dfs(d, kv, s, ans, i + 1)\n",
    "        s_c = d[kv[i][0]]\n",
    "        if not s.intersection(s_c):\n",
    "            res += self.dfs(d, kv, s.union(s_c), ans * kv[i][1], i + 1)\n",
    "        return res % int(1e9 + 7)\n",
    "\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        d = {1: set(), 2: {2}, 3: {3}, 5: {5}, 6: {2, 3}, 7: {7},\n",
    "             10: {2, 5}, 11: {11}, 13: {13}, 14: {2, 7}, 15: {3, 5},\n",
    "             17: {17}, 19: {19}, 21: {3, 7}, 22: {2, 11}, 23: {23},\n",
    "             26: {2, 13}, 29: {29}, 30: {2, 3, 5}}\n",
    "        d2 = {}\n",
    "        M = int(1e9 + 7)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d2[num] = d2.get(num, 0) + 1\n",
    "        x = d2.pop(1, 0)\n",
    "        y = 1\n",
    "        for _ in range(x): y = (y * 2) % M\n",
    "        if not d2: return 0\n",
    "        kv = list(d2.items())\n",
    "        for i in range(len(kv)):\n",
    "            k, v = kv[i]\n",
    "            res = (res + self.dfs(d, kv, d[k].copy(), v, i + 1)) % M\n",
    "        return (res * y) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        lst=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(n):\n",
    "            state = 0\n",
    "            for i, x in enumerate(lst):\n",
    "                while n > 0 and n % x == 0:\n",
    "                    if (state >> i) & 1 == 1:\n",
    "                        return False,state\n",
    "                    state |= (1 << i)\n",
    "                    n //= x\n",
    "                    if n == 1:\n",
    "                        return True,state\n",
    "\n",
    "        cnt=Counter(nums)\n",
    "        mask=1<<10\n",
    "        f=[0]*mask\n",
    "        f[0]=1\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        for i in range(2,31):\n",
    "            if i not in cnt:\n",
    "                continue\n",
    "            (flag,cur)=check(i)\n",
    "            if flag==False:\n",
    "                continue\n",
    "            for pre in range(mask-1,-1,-1):\n",
    "                if (pre&cur) != 0:\n",
    "                    continue\n",
    "                s=pre|cur\n",
    "                f[s]+=f[pre]*cnt[i]%mod\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(1,mask):\n",
    "            ans=(ans+f[i])%mod\n",
    "        if 1 in cnt:\n",
    "            ans=(ans*2**cnt[1])%mod\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力枚举失败\n",
    "        # def f(n):\n",
    "        #     state=0\n",
    "        #     count=0\n",
    "        #     for i,x in enumerate(lst):\n",
    "        #         while n>0 and n%x==0:\n",
    "        #             if (state>>i)&1==1:\n",
    "        #                 return False\n",
    "        #             state|=(1<<i)\n",
    "        #             n//=x\n",
    "        #             if n==1:\n",
    "        #                 return True\n",
    "                \n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if f(res) else 0\n",
    "        #     a=dfs(i-1,res)\n",
    "        #     b=dfs(i-1,res*nums[i])\n",
    "        #     return a+b\n",
    "        # return dfs(n-1,1)\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    if x % 2 == 0:\n",
    "        ans.add(2)\n",
    "        while x % 2 == 0:\n",
    "            x //= 2\n",
    "    d = 3\n",
    "    while d ** 2 <= x:\n",
    "        if x % d == 0:\n",
    "            ans.add(d)\n",
    "            while x % d == 0:\n",
    "                x //= d\n",
    "        d += 2\n",
    "    if x > 1: ans.add(x)\n",
    "    return ans\n",
    "\n",
    "my_primes = defaultdict(set)\n",
    "for i in range(2, 31):\n",
    "    my_primes[i] = f(i)\n",
    "candidate = {2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30}\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        cnt1 = nums.count(1)\n",
    "        nums = list(filter(lambda p: p in candidate, nums))\n",
    "        cnt = Counter(nums)\n",
    "        L = sorted(set(nums))\n",
    "        n = len(L)\n",
    "        mod = 10 ** 9 + 7\n",
    "        rest = 0\n",
    "\n",
    "        def dfs(i, my_set, arr, val):\n",
    "            nonlocal rest\n",
    "            if i == n:\n",
    "                rest += val\n",
    "                return\n",
    "            tmp_set = f(L[i])\n",
    "            if not (tmp_set & my_set):\n",
    "                dfs(i + 1, tmp_set | my_set, arr + [L[i]], val * cnt[L[i]] % mod)\n",
    "            dfs(i + 1, my_set, arr, val)\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(i + 1, f(L[i]), [L[i]], cnt[L[i]])\n",
    "        return (pow(2, cnt1, mod) * rest) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumberTheoryPrimeFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil + 100\n",
    "        self.prime_factor = [[] for _ in range(self.ceil + 1)]\n",
    "        self.min_prime = [0] * (self.ceil + 1)\n",
    "        self.get_min_prime_and_prime_factor()\n",
    "        return\n",
    "\n",
    "    def get_min_prime_and_prime_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            if not self.min_prime[i]:\n",
    "                self.min_prime[i] = i\n",
    "                for j in range(i * i, self.ceil + 1, i):\n",
    "                    if not self.min_prime[j]:\n",
    "                        self.min_prime[j] = i\n",
    "\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）\n",
    "        for num in range(2, self.ceil + 1):\n",
    "            i = num\n",
    "            while num > 1:\n",
    "                p = self.min_prime[num]\n",
    "                cnt = 0\n",
    "                while num % p == 0:\n",
    "                    num //= p\n",
    "                    cnt += 1\n",
    "                self.prime_factor[i].append([p, cnt])\n",
    "        return\n",
    "\n",
    "    def comb(self, n, m):\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(1, n+1):  # n!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] += y\n",
    "        for i in range(1, m+1):  # m!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "        for i in range(1, n-m+1):  # (n-m)!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "\n",
    "        ans = 1\n",
    "        for w in cnt:\n",
    "            ans *= w**cnt[w]\n",
    "        return ans\n",
    "\n",
    "\n",
    "nt = NumberTheoryPrimeFactor(32)\n",
    "nums = [x for x in range(1, 32) if all(c<=1 for _, c in nt.prime_factor[x])]\n",
    "dct = set(nums)\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        mod = 10**9 + 7\n",
    "        pre = defaultdict(int)\n",
    "        for num in cnt:\n",
    "            if num == 1 or num not in dct:\n",
    "                continue\n",
    "            cur = pre.copy()\n",
    "            for p in pre:\n",
    "                if math.gcd(p, num) == 1:\n",
    "                    cur[p*num] += pre[p]*cnt[num]\n",
    "                    cur[p * num] %= mod\n",
    "            pre = cur.copy()\n",
    "            pre[num] += cnt[num]\n",
    "        ans = sum(pre.values())\n",
    "        ans *= pow(2, cnt[1], mod)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        # 预处理\n",
    "        special = set([1, 17, 19, 23, 29])\n",
    "        mp = defaultdict(int)\n",
    "        for x in nums:\n",
    "            if x in special:\n",
    "                mp[x] += 1\n",
    "\n",
    "        p = set([2, 3, 5, 7, 11, 13])\n",
    "        FULL = (1 << 6) - 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        # 预处理nums 去掉非质数\n",
    "        ban = set([4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 1, 17, 19, 23, 29])\n",
    "        nums = [x for x in nums if x not in ban] \n",
    "        cnt = Counter(nums)\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == n or mask == FULL:\n",
    "                return 1 if mask > 0 else 0\n",
    "            # 不选\n",
    "            res = dfs(i + 1, mask)\n",
    "            # 选\n",
    "            # 情况1. 是质数\n",
    "            if nums[i] in p and (mask >> nums[i]) & 1 == 0:\n",
    "                res += dfs(i + 1, mask | (1 << nums[i])) * cnt[nums[i]]\n",
    "            elif nums[i] not in p:\n",
    "                # 情况2. 不是质数\n",
    "                match nums[i]:\n",
    "                    case 6:\n",
    "                        if (mask >> 2) & 1 == 0 and (mask >> 3) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 2) | (1 << 3)) * cnt[nums[i]]\n",
    "                    case 10:\n",
    "                        if (mask >> 2) & 1 == 0 and (mask >> 5) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 2) | (1 << 5)) * cnt[nums[i]]\n",
    "                    case 14:\n",
    "                        if (mask >> 2) & 1 == 0 and (mask >> 7) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 2) | (1 << 7)) * cnt[nums[i]]\n",
    "                    case 15:\n",
    "                        if (mask >> 3) & 1 == 0 and (mask >> 5) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 3) | (1 << 5)) * cnt[nums[i]]\n",
    "                    case 21:\n",
    "                        if (mask >> 3) & 1 == 0 and (mask >> 7) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 3) | (1 << 7)) * cnt[nums[i]]\n",
    "                    case 22:\n",
    "                        if (mask >> 2) & 1 == 0 and (mask >> 11) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 2) | (1 << 11)) * cnt[nums[i]]\n",
    "                    case 26:\n",
    "                        if (mask >> 2) & 1 == 0 and (mask >> 13) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 2) | (1 << 13)) * cnt[nums[i]]\n",
    "                    case 30:\n",
    "                        if (mask >> 2) & 1 == 0 and (mask >> 3) & 1 == 0 and (mask >> 5) & 1 == 0:\n",
    "                            res += dfs(i + 1, mask | (1 << 2) | (1 << 3) | (1 << 5)) * cnt[nums[i]]\n",
    "            return res % MOD\n",
    "\n",
    "        # 特殊处理\n",
    "        ans = dfs(0, 0)\n",
    "        for k, v in mp.items():\n",
    "            if k != 1 and v != 0:\n",
    "                ans = ((ans + 1) * (v + 1) - 1) % MOD\n",
    "        \n",
    "        ans = (ans * pow(2, mp[1], MOD)) % MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        onecnt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                onecnt += 1\n",
    "                continue\n",
    "            m1[i] += 1\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        def has_dup(list1):\n",
    "            return len(list1) != len(set(list1))\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            tl = prime_factors(i)\n",
    "            if has_dup(tl):\n",
    "                continue\n",
    "            fz = frozenset(prime_factors(i))\n",
    "            m2[fz] = m1[i]\n",
    "\n",
    "        keylist = sorted(list(m2.keys()))\n",
    "        mod1 = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(idx, fz):\n",
    "            if idx == len(keylist):\n",
    "                if len(fz) == 0:\n",
    "                    return 0\n",
    "                return 1\n",
    "            cur_fz = keylist[idx]\n",
    "            ans = 0\n",
    "            ans += get_cnt(idx + 1, fz)\n",
    "            if fz.isdisjoint(cur_fz):\n",
    "                ans += get_cnt(idx + 1, fz.union(cur_fz)) * m2[cur_fz]\n",
    "            return ans % mod1\n",
    "\n",
    "        ret1 = get_cnt(0, frozenset({}))\n",
    "        if onecnt > 0:\n",
    "            ret1 = (ret1 * (2 ** onecnt)) % mod1\n",
    "        return ret1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        onecnt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                onecnt += 1\n",
    "                continue\n",
    "            m1[i] += 1\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        def has_dup(list1):\n",
    "            return len(list1) != len(set(list1))\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            tl = prime_factors(i)\n",
    "            if has_dup(tl):\n",
    "                continue\n",
    "            fz = frozenset(prime_factors(i))\n",
    "            m2[fz] = m1[i]\n",
    "\n",
    "        keylist = sorted(list(m2.keys()))\n",
    "        mod1 = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(idx, fz):\n",
    "            if idx == len(keylist):\n",
    "                if len(fz) == 0:\n",
    "                    return 0\n",
    "                return 1\n",
    "            cur_fz = keylist[idx]\n",
    "            ans = 0\n",
    "            ans += get_cnt(idx + 1, fz)\n",
    "            if fz.isdisjoint(cur_fz):\n",
    "                ans += get_cnt(idx + 1, fz.union(cur_fz)) * m2[cur_fz]\n",
    "            return ans % mod1\n",
    "\n",
    "        ret1 = get_cnt(0, frozenset({}))\n",
    "        if onecnt > 0:\n",
    "            ret1 = (ret1 * (2 ** onecnt)) % mod1\n",
    "        return ret1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.numberOfGoodSubsets([2, 2, 3, 4, 3, 4]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        onecnt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                onecnt += 1\n",
    "                continue\n",
    "            m1[i] += 1\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        def has_dup(list1):\n",
    "            return len(list1) != len(set(list1))\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            tl = prime_factors(i)\n",
    "            if has_dup(tl):\n",
    "                continue\n",
    "            fz = frozenset(prime_factors(i))\n",
    "            m2[fz] = m1[i]\n",
    "\n",
    "        keylist = sorted(list(m2.keys()))\n",
    "        mod1 = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(idx, fz):\n",
    "            if idx == len(keylist):\n",
    "                if len(fz) == 0:\n",
    "                    return 0\n",
    "                return 1\n",
    "            cur_fz = keylist[idx]\n",
    "            ans = get_cnt(idx + 1, fz)\n",
    "            if fz.isdisjoint(cur_fz):\n",
    "                ans += get_cnt(idx + 1, fz.union(cur_fz)) * m2[cur_fz]\n",
    "            return ans % mod1\n",
    "\n",
    "        return (get_cnt(0, frozenset({})) * (2 ** onecnt)) % mod1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        onecnt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                onecnt += 1\n",
    "                continue\n",
    "            m1[i] += 1\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        def has_dup(list1):\n",
    "            return len(list1) != len(set(list1))\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            tl = prime_factors(i)\n",
    "            if has_dup(tl):\n",
    "                continue\n",
    "            fz = frozenset(prime_factors(i))\n",
    "            m2[fz] = m1[i]\n",
    "\n",
    "        keylist = sorted(list(m2.keys()))\n",
    "        mod1 = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(idx, fz):\n",
    "            if idx == len(keylist):\n",
    "                if len(fz) == 0:\n",
    "                    return 0\n",
    "                return 1\n",
    "            cur_fz = keylist[idx]\n",
    "            ans = get_cnt(idx + 1, fz)\n",
    "            if fz.isdisjoint(cur_fz):\n",
    "                ans += get_cnt(idx + 1, fz.union(cur_fz)) * m2[cur_fz]\n",
    "            return ans % mod1\n",
    "\n",
    "        return (get_cnt(0, frozenset({})) * (2 ** onecnt)) % mod1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        onecnt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                onecnt += 1\n",
    "                continue\n",
    "            m1[i] += 1\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        def has_dup(list1):\n",
    "            return len(list1) != len(set(list1))\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            tl = prime_factors(i)\n",
    "            if has_dup(tl):\n",
    "                continue\n",
    "            fz = frozenset(prime_factors(i))\n",
    "            m2[fz] = m1[i]\n",
    "\n",
    "        keylist = sorted(list(m2.keys()))\n",
    "        mod1 = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(idx, fz):\n",
    "            if idx == len(keylist):\n",
    "                if len(fz) == 0:\n",
    "                    return 0\n",
    "                return 1\n",
    "            cur_fz = keylist[idx]\n",
    "            ans = get_cnt(idx + 1, fz)\n",
    "            if fz.isdisjoint(cur_fz):\n",
    "                ans += get_cnt(idx + 1, fz.union(cur_fz)) * m2[cur_fz]\n",
    "            return ans % mod1\n",
    "\n",
    "        return (get_cnt(0, frozenset({})) * (2 ** onecnt)) % mod1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        onecnt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                onecnt += 1\n",
    "                continue\n",
    "            m1[i] += 1\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        def has_dup(list1):\n",
    "            return len(list1) != len(set(list1))\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            tl = prime_factors(i)\n",
    "            if has_dup(tl):\n",
    "                continue\n",
    "            fz = frozenset(prime_factors(i))\n",
    "            m2[fz] = m1[i]\n",
    "\n",
    "        keylist = sorted(list(m2.keys()))\n",
    "        mod1 = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(idx, fz):\n",
    "            if idx == len(keylist):\n",
    "                if len(fz) == 0:\n",
    "                    return 0\n",
    "                return 1\n",
    "            cur_fz = keylist[idx]\n",
    "            ans = 0\n",
    "            ans += get_cnt(idx + 1, fz)\n",
    "            if fz.isdisjoint(cur_fz):\n",
    "                ans += get_cnt(idx + 1, fz.union(cur_fz)) * m2[cur_fz]\n",
    "            return ans % mod1\n",
    "\n",
    "        return (get_cnt(0, frozenset({})) * (2 ** onecnt)) % mod1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "n=len(prime)\n",
    "def decom(num):\n",
    "    mask=0\n",
    "    for i in range(n):\n",
    "        if num%prime[i]==0: mask|=(1<<i)\n",
    "    return mask\n",
    "def check(num):\n",
    "    for p in prime:\n",
    "        if num%(p*p)==0 or num==1: return False\n",
    "    return True\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        #考虑将每一个元素质因数分解\n",
    "        #状态压缩，将质因数存在形式表达为二进制数\n",
    "        #先清理数组中的含有平方的数\n",
    "        #记忆化搜索\n",
    "        nums=Counter(nums)\n",
    "        count_1=nums[1]\n",
    "        nums=[(i,v) for i,v in nums.items() if check(i)]\n",
    "        m=len(nums)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==m: return 1\n",
    "            res=0\n",
    "            res+=dfs(i+1,mask)\n",
    "            new_mask=decom(nums[i][0])\n",
    "            if mask&new_mask==0:\n",
    "                res+=dfs(i+1,mask|new_mask)*nums[i][1]\n",
    "            return res%MOD\n",
    "        res=dfs(0,0)\n",
    "        return ((res-1)*(2**count_1))%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "n=len(prime)\n",
    "def decom(num):\n",
    "    mask=0\n",
    "    for i in range(n):\n",
    "        if num%prime[i]==0: mask|=(1<<i)\n",
    "    return mask\n",
    "def check(num):\n",
    "    for p in prime:\n",
    "        if num%(p*p)==0 or num==1: return False\n",
    "    return True\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        #考虑将每一个元素质因数分解\n",
    "        #状态压缩，将质因数存在形式表达为二进制数\n",
    "        #先清理数组中的含有平方的数\n",
    "        nums=Counter(nums)\n",
    "        count_1=nums[1]\n",
    "        nums=[(i,v) for i,v in nums.items() if check(i)]\n",
    "        m=len(nums)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==m: return 1\n",
    "            res=0\n",
    "            res+=dfs(i+1,mask)\n",
    "            new_mask=decom(nums[i][0])\n",
    "            if mask&new_mask==0:\n",
    "                res+=dfs(i+1,mask|new_mask)*nums[i][1]\n",
    "            return res%MOD\n",
    "        res=dfs(0,0)\n",
    "        return ((res-1)*(2**count_1))%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "n=len(prime)\n",
    "def decom(num):\n",
    "    mask=0\n",
    "    for i in range(n):\n",
    "        if num%prime[i]==0: mask|=(1<<i)\n",
    "    return mask\n",
    "def check(num):\n",
    "    for p in prime:\n",
    "        if num%(p*p)==0 or num==1: return False\n",
    "    return True\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "        #考虑将每一个元素质因数分解\n",
    "        #状态压缩，将质因数存在形式表达为二进制数\n",
    "        #先清理数组中的含有平方的数\n",
    "        nums=Counter(nums)\n",
    "        count_1=nums[1]\n",
    "        nums=[(i,v) for i,v in nums.items() if check(i)]\n",
    "        m=len(nums)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==m: return 1\n",
    "            res=0\n",
    "            res+=dfs(i+1,mask)\n",
    "            new_mask=decom(nums[i][0])\n",
    "            if mask&new_mask==0:\n",
    "                res+=dfs(i+1,mask|new_mask)*nums[i][1]\n",
    "            return res%MOD\n",
    "        res=dfs(0,0)\n",
    "        return ((res-1)*(2**count_1))%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    " \n",
    "        single = [2,3,5,7,11,13,17,19,23,29]\n",
    "        counter = Counter(nums)\n",
    "        MOD = 10**9+7 \n",
    "        def getMask(n):\n",
    "            ret = 0\n",
    "            for i in range(len(single)):\n",
    "                div = single[i]\n",
    "                if n<div:\n",
    "                    break \n",
    "                if n%div==0:\n",
    "                    if n%(div**2)==0:\n",
    "                        return 0 \n",
    "                    ret = ret|(1<<(i+1))\n",
    "            # print(n,ret)\n",
    "            return ret \n",
    "        keys = [k for k in counter.keys() if getMask(k)>0]\n",
    "        stack = []\n",
    "        ret = 0\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==len(keys):\n",
    "                return 0 \n",
    "            k = keys[i]\n",
    "            nmask = getMask(k)\n",
    "            sret = 0\n",
    "            if mask&nmask==0:\n",
    "                sret = (dfs(i+1,mask|nmask)*counter[k]+counter[k])%MOD\n",
    "            sret = (dfs(i+1,mask)+sret)%MOD\n",
    "\n",
    "            return sret\n",
    "        ret = dfs(0,0)\n",
    "        # print(keys,counter,ret)\n",
    "        if 1 in counter:\n",
    "            # c33+c32+c31\n",
    "            ret = ret*(2**counter[1])%MOD \n",
    "        return ret \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    " \n",
    "        single = [2,3,5,7,11,13,17,19,23,29]\n",
    "        counter = Counter(nums)\n",
    "        MOD = 10**9+7 \n",
    "        def getMask(n):\n",
    "            ret = 0\n",
    "            for i in range(len(single)):\n",
    "                div = single[i]\n",
    "                if n<div:\n",
    "                    break \n",
    "                if n%div==0:\n",
    "                    if n%(div**2)==0:\n",
    "                        return 0 \n",
    "                    ret = ret|(1<<(i+1))\n",
    "            # print(n,ret)\n",
    "            return ret \n",
    "        keys = [(k,getMask(k)) for k in counter.keys() if getMask(k)>0]\n",
    "        stack = []\n",
    "        ret = 0\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==len(keys):\n",
    "                return 0 \n",
    "            k,nmask = keys[i]\n",
    "            sret = 0\n",
    "            if mask&nmask==0:\n",
    "                sret = (dfs(i+1,mask|nmask)*counter[k]+counter[k])%MOD\n",
    "            sret = (dfs(i+1,mask)+sret)%MOD\n",
    "\n",
    "            return sret\n",
    "        ret = dfs(0,0)\n",
    "        # print(keys,counter,ret)\n",
    "        if 1 in counter:\n",
    "            # c33+c32+c31\n",
    "            ret = ret*(2**counter[1])%MOD \n",
    "        return ret \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    " \n",
    "        single = [2,3,5,7,11,13,17,19,23,29]\n",
    "        counter = Counter(nums)\n",
    "        MOD = 10**9+7 \n",
    "        def getMask(n):\n",
    "            ret = 0\n",
    "            for i in range(len(single)):\n",
    "                div = single[i]\n",
    "                if n<div:\n",
    "                    break \n",
    "                if n%div==0:\n",
    "                    if n%(div**2)==0:\n",
    "                        return 0 \n",
    "                    ret = ret|(1<<(i+1))\n",
    "            # print(n,ret)\n",
    "            return ret \n",
    "        keys = [k for k in counter.keys() if getMask(k)>0]\n",
    "        stack = []\n",
    "        ret = 0\n",
    "        dp = {}\n",
    "        @cache\n",
    "        def dfs(i,mask,ans):\n",
    "            if i==len(keys):\n",
    "                return 0 \n",
    "            k = keys[i]\n",
    "            nmask = getMask(k)\n",
    "            sret = 0\n",
    "            if mask&nmask==0:\n",
    "                curAns = ans*counter[k]%MOD\n",
    "                sret = (dfs(i+1,mask|nmask,curAns)+curAns)%MOD\n",
    "            sret = (dfs(i+1,mask,ans)+sret)%MOD\n",
    "\n",
    "            return sret\n",
    "        ret = dfs(0,0,1)\n",
    "        # print(keys,counter,ret)\n",
    "        if 1 in counter:\n",
    "            # c33+c32+c31\n",
    "            ret = ret*(2**counter[1])%MOD \n",
    "        return ret \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfGoodSubsets(self, nums: List[int]) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == 31:\n",
    "             return 1 if j > 1 else 0\n",
    "          res = dfs(i + 1, j)\n",
    "          if i == 1:\n",
    "             res += (pow(2, cnts[i], MOD) - 1) * dfs(i + 1, j | 1)\n",
    "             res %= MOD\n",
    "          elif masks[i] != -1 and (masks[i] & j) == 0:\n",
    "             res += cnts[i] * dfs(i + 1, masks[i] | j)\n",
    "             res %= MOD\n",
    "          return res\n",
    "       primes = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "       dic = collections.defaultdict(int)\n",
    "       for i, p in enumerate(primes):\n",
    "          dic[p] = i\n",
    "       cnts = [0] * 31\n",
    "       for num in nums:\n",
    "          cnts[num] += 1\n",
    "       masks = [0] * 31\n",
    "       for i in range(1, 31):\n",
    "          if i in dic.keys():\n",
    "             masks[i] = 1 << dic[i]\n",
    "          elif i % 4 == 0 or i % 9 == 0 or i % 25 == 0:\n",
    "             masks[i] = -1\n",
    "          else:\n",
    "             for j in range(2, i + 1):\n",
    "                if j in dic.keys() and i % j == 0:\n",
    "                   masks[i] |= 1 << dic[j]\n",
    "       return dfs(1, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
